package data_structure.leetcode;

public class Solution75 {


    public void sortColors(int []nums){
        sortColors (nums,0,nums.length-1);
    }

    private void sortColors(int[] nums,int left,int right) {

        //0,1,2
        //[1,lt],[lt+1,i-1],[gt,nums.length-1]
        int i=left+1;
        int lt=left;
        int gt=right + 1;

        while(i<gt){

            if(nums[i]<nums[left]){
                lt++;
                swap (nums,i,lt);
                i++;
            }else if(nums[i] >nums[left]){
                gt--;
                swap(nums, i, gt);
            }else{
                i++;
            }
        }
        swap (nums,left,lt);
        sortColors (nums,left,lt-1);
        sortColors (nums,gt,right);
    }

    private void swap(int []arr,int left,int right){
        int temp=arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }
}
